package problems.practice;

import utils.beans.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 103. 二叉树的锯齿形层序遍历
 * <p>https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
 * <p>
 * @author habitplus
 * @since 2022/8/14 20:14
 */
public class T103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        List<List<Integer>> ret = new ArrayList<>();
//        if (root == null) return null;
        Queue<TreeNode> que = new LinkedList<>();
        boolean ltr = true;
        TreeNode node;

        if (root != null)
            que.offer(root);

        while (!que.isEmpty()) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = que.size(); i > 0; --i) {
                node = que.poll();
                if (ltr) list.addLast(node.val);
                else list.addFirst(node.val);

                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            ltr = !ltr;
            ret.add(list);
        }
        return ret;
    }
}
